package com.gjx.leetcode;

import java.util.ArrayList;
import java.util.List;

//131. 分割回文串
//
//给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
//
//返回 s 所有可能的分割方案。
//
//示例:
//
//输入: "aab"
//输出:
//[
//  ["aa","b"],
//  ["a","a","b"]
//]
//

public class Solution131 {
	public List<List<String>> partition(String s) {
		return partition(s.toCharArray(), 0);
	}
	
	private List<List<String>> partition(char[] c, int start) {
		List<List<String>> res = new ArrayList<>();
		if (start >= c.length) {
			res.add(new ArrayList<>());
			return res;
		} else if (start == c.length-1) {
			List<String> list = new ArrayList<>();
			list.add(new String(c, start, 1));
			res.add(list);
			return res;
		}
		
		for (int i=start; i<c.length; i++) {
			if (isValid(c, start, i)) {
				
				String cur = new String(c, start, i-start+1);
				
				for (List<String> list : partition(c, i+1)) {
					list.add(0,cur);
					res.add(list);
				}
				
			}
		}
		return res;
	}
	
	private boolean isValid(char[] c, int i, int j) {
		if (i == j) {
			return true;
		}
		while (i < j) {
			if (c[i] == c[j]) {
				i++;
				j--;
			} else {
				return false;
			}
		}
		return true;
	}
	
}
